\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\begin{itemize}
\item
  排列，每次从中删除一个元素，一个删除 \(m\) 次，求每次删除后的逆序对数
\item
  时、空复杂度 \(O(nlog^2n)\)
\end{itemize}

\begin{lstlisting}
#define rep(i , a , b) for(int i = a ; i <= b ; i ++)
#define ll long long
const int N = 1e5 + 10 , M = 3e7 + 10;
int n , m , tot;
ll ans;
int lowbit(int x){
	return x & (-x);
}
int a[N] , pos[N] , quea[N] , queb[N];
int root[N];
struct Ctree{
	int l , r , sum;
}tree[M];
void change(int &root , int l , int r , int x , int y)
{
	if(!root) root = ++ tot;
	tree[root].sum += y;
	if(l == r) return;
	int mid = (l + r) >> 1;
	if(x <= mid) change(tree[root].l , l , mid , x , y);
	else change(tree[root].r , mid + 1 , r , x , y);
}
int query(int l , int r , int x , int mode)
{
	int cnta = 0 , cntb = 0 , sum = 0;
	for(int i = l - 1 ; i ; i -= lowbit(i)) quea[++ cnta] = root[i];
	for(int i = r ; i ; i -= lowbit(i)) 	queb[++ cntb] = root[i];
	l = 1 , r = n;
	while(l != r)
	{
		int mid = (l + r) >> 1;
		if(x > mid)
		{
			if(mode)
			{
				rep(i , 1 , cnta) sum -= tree[tree[quea[i]].l].sum;
				rep(i , 1 , cntb) sum += tree[tree[queb[i]].l].sum;
			}
			rep(i , 1 , cnta) quea[i] = tree[quea[i]].r;
			rep(i , 1 , cntb) queb[i] = tree[queb[i]].r;
			l = mid + 1;
		}
		else
		{
			if (!mode)
			{
				rep(i , 1 , cnta) sum -= tree[tree[quea[i]].r].sum;
				rep(i , 1 , cntb) sum += tree[tree[queb[i]].r].sum;
			}
			rep(i , 1 , cnta) quea[i] = tree[quea[i]].l;
			rep(i , 1 , cntb) queb[i] = tree[queb[i]].l;
			r = mid;
		}
	}
	return sum;
}
signed main()
{
	cin >> n >> m;
	rep(i , 1 , n)
	{
		cin >> a[i];
		pos[a[i]] = i;
		ans += query(1 , i - 1 , a[i] , 0);
		for(int j = i ; j <= n ; j += lowbit(j)) change(root[j] , 1 , n , a[i] , 1);
	}
	cout << ans << '\n';
	rep(i , 1 , m - 1)
	{
		int x;
		cin >> x;
		ans -= query(1 , pos[x] - 1 , x , 0);
		ans -= query(pos[x] + 1 , n , x , 1);
		cout << ans << '\n';
		for(int j = pos[x] ; j <= n ; j += lowbit(j)) change(root[j] , 1 , n , x , -1);
	}
	return 0;
}
\end{lstlisting}

\end{document}
